/**
 * 二分法查找数字
 */

#include <stdio.h>
#include <time.h>

#define MAX_ELEMENT 1000

int binsearch(int x, int v[], int n);
int binsearch2(int x, int v[], int n);

int main() {
    int i, n, index;
    int testdata[MAX_ELEMENT];
    clock_t time_taken;

    for (i = 0; i < MAX_ELEMENT; i++)
        testdata[i] = i;

    n = 20;
    for (i = 0, time_taken = clock(); i < 100000; i++)
        index = binsearch(n, testdata, MAX_ELEMENT);
    time_taken = clock() - time_taken;

    if ( index < 0)
        printf("Element %d not found!\n", n);
    else
        printf("Element %d have found at %d\n", n, index);

    printf("binsearch() has take %lu clocks ( %lu seconds ).\n", time_taken, time_taken / CLOCKS_PER_SEC);

    for (i = 0, time_taken = clock(); i < 100000; i++)
        index = binsearch2(n, testdata, MAX_ELEMENT);
    time_taken = clock() - time_taken;

    if ( index < 0)
        printf("Element %d not found!\n", n);
    else
        printf("Element %d have found at %d\n", n, index);

    printf("binsearch2() has take %lu clocks ( %lu seconds ).\n", time_taken, time_taken / CLOCKS_PER_SEC);



    return 0;
}

// 每次循环中判断两次
int binsearch(int x, int v[], int n) {
    int low, high, mid;
    low = 0;
    high = n-1;
    while (low <= high) {
        mid = (low + high) / 2;
        if (x < v[mid])
            high = mid - 1;
        else if ( x > v[mid])
            low = mid + 1;
        else
            return mid;
    }

    return -1;
}

// 每次循环中判断一次
int binsearch2(int x, int v[], int n) {
    int low, high, mid;
    low = 0;
    high = n-1;
    while (low < high) {
        mid = (low + high) / 2;
        if (x <= v[mid])
            high = mid;
        else
            low = mid + 1;
    }
    return (x == v[low])? low : -1;
}
